//
// Created by Administrator on 2021/11/12.
//
#define MaxSize 100//定义队列中元素的最大个数
#define ElemType int
/*定义顺序队列*/
typedef struct {
    ElemType data[MaxSize];//用静态数组字放队列元素
    int front, rear;//队头指针和队尾指针
    int size;//当前队列长度(方案2)
    int tag;//最近进行的操作：删除（0）/插入（1）（方案3）
} SqQueue;
/*front=队头元素
 * rear=第一个需要插入元素的位置*/

/*方案2：
 * 插入成功：size++
 * 删除成功：size--
 * 判满条件：size==MaxSize
 * 判空条件：size==0*/

/*方案3：
 * 删除成功：令tag=0
 * 插入成功：令tag=1
 * 队满条件：front==rear && tag ==1
 * 判空条件：front==rear && tag ==0*/

/*初始化队列*/
void InitQueue(SqQueue &Q) {
    Q.rear = Q.front = 0;//初始时队头、队尾指针指向0
    Q.size = 0;//方案2
    Q.tag = 0;//方案3
}

/*判断队列是否为空*/
bool QueueEmpty(SqQueue Q) {
    return Q.rear == Q.front;
}

/*入队*/
bool EnQueue(SqQueue &Q, ElemType x) {
    if ((Q.rear + 1) % MaxSize == Q.front) {
        //只牺牲最后一个空间（判满条件）,否则盘满和判空冲突
        return false;//队满则报错
    }
    Q.data[Q.rear] = x;//将x插入队尾
    Q.rear = (Q.rear + 1) % MaxSize;//队尾指针后移
    return true;
}

/*出队(删除一个队头元素，并用x返回)*/
bool DeQueue(SqQueue &Q, ElemType &x) {
    if (Q.rear == Q.front) {
        return false; //队空则报错
    }
    x = Q.data[Q.front];//获取队头元素
    Q.front = (Q.front + 1) % MaxSize;
    return true;
}

/*获得队头元素的值，用x返回*/
bool GetHead(SqQueue Q, ElemType &x) {
    if (Q.rear == Q.front) {
        return false; //队空则报错
    }
    x = Q.data[Q.front];//获取队头元素
    return true;
}
/*队列元素个数:
(rear+MaxSize-front)%MaxSize
*/
/*注意队尾指针指向的位置：
 * 判空条件会有所不同*/

